var partition = function (head, x) {
  const leftNode = new ListNode(0);
  let left = leftNode; // 指针
  const rightNode = new ListNode(0);
  let right = rightNode; // 指针
  while (head !== null) {
    if (head.val < x) {
      left.next = head;
      left = left.next; // 确保每次挂载在before的最后一个元素上
    } else {
      right.next = head;
      right = right.next;
    }
    head = head.next; // key step: keep changing head till it fails the condition.
  }
  right.next = null; //key step: make sure there's no link loop
  left.next = rightNode.next; // before,after_head to remark the head of before and after.
  return leftNode.next;
};
